#define DetailedRouteTracing
#define RouteCalculatorSpeedup
#define Use64BitArray
//#define UseSingle64Bit	// CAUTION - this will throw exception if > 64 bits needed

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Xml.Serialization;
using System.Diagnostics;

namespace WebApplication
{
	/// <summary>
	/// Summary description for Route.
	/// </summary>
	[Serializable]
	public class RouteCollection : ICollection
	{
		public int TotalValue
		{
			get
			{
				int total = 0;
				foreach (Route rt in _aRoutes)
					total += rt.Value;
				return (total);
			}
		}

		public int CachedTotalValue;	// used by route calculator
#if UseSingle64Bit
		public ulong ORedRouteBitArray;	// used by route calculator (this is all routes ORed together)
#elif Use64BitArray
		public ulong[] ORedRouteBitArray;	// used by route calculator (this is all routes ORed together)
#else
		public int[] ORedRouteBitArray;	// used by route calculator (this is all routes ORed together)
#endif

		//private ArrayList  _aRoutes;
		private List<Route> _aRoutes;

		public Route this [int index]   // indexer declaration
		{ 
			get
			{
				return (Route) _aRoutes[index];
			}

			set
			{
				_aRoutes[index] = value;
			}
		}

		public void CopyTo(Array a, int index)
		{
			_aRoutes.ToArray().CopyTo(a, index);
		}
		public object SyncRoot
		{
			get{return this;}
		}
		public bool IsSynchronized
		{
			get{return false;}
		}

		public int Count
		{
			get
			{
				return _aRoutes.Count;
			}
		}

		public RouteCollection ()
		{
			//_aRoutes = new ArrayList ();
			_aRoutes = new List<Route>();
		}
		public RouteCollection (RouteCollection source)
		{
			//_aRoutes = (ArrayList) source._aRoutes.Clone ();
			_aRoutes = new List<Route>(source._aRoutes);
		}

		//public void Add (System.Object Route)
		//{
		//	_aRoutes.Add (Route);
		//}

		public void Add (Route Route)
		{
			_aRoutes.Add (Route);
		}

		public void AddRoutes (RouteCollection Routes)
		{
			foreach (Route route in Routes)
				Add (route);
		}

		public void AddNonConflictingRoutes (RouteCollection Routes)
		{
			foreach (Route route in Routes)
			{
				if (! route.ConflictsWith (this))
					Add (route);
			}
		}

		public void Remove (Route Route)
		{
			_aRoutes.Remove (Route);
		}


		// IEnumerable Interface Implementation:
		public IEnumerator GetEnumerator() // non-IEnumerable version
		{
			return _aRoutes.GetEnumerator ();
		}

		IEnumerator IEnumerable.GetEnumerator() // IEnumerable version
		{
			//			return (IEnumerator) new ShareEnumerator(this);
			return _aRoutes.GetEnumerator ();
		}

		public override string ToString ()
		{
			StringBuilder sb = new StringBuilder ();
			if (_aRoutes.Count == 0)
				sb.Append ("No routes");
			else
			{
				for (int i=0; i < _aRoutes.Count; i++)
				{
					if (i > 0)
						sb.Append ("\n");
					((Route) _aRoutes[i]).ToString (sb);
				}
			}
			return sb.ToString ();
		}

		public string ToStringTerse(string lineBreak)
		{
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < _aRoutes.Count; i++)
			{
				if (i > 0)
					sb.Append(lineBreak);
				((Route)_aRoutes[i]).ToStringTerse(sb);
			}
			return sb.ToString();
		}

		//static RouteCollection GetRoutesContainingToken (PublicCompany company)
		//{
		//    City [] cities = City.GetAllCities (company);
		//    return BuildRoutes (company, cities, true);
		//}

		//static RouteCollection GetRoutesOriginatingAtToken (PublicCompany company)
		//{
		//    City [] cities = City.GetAllTokenedCities (company);
		//    return BuildRoutes (company, cities, true);
		//}

		//static RouteCollection BuildRoutes (PublicCompany company, City [] StartCities, bool MustContainToken)
		//{
		//	return BuildRoutes (company, StartCities, MustContainToken, false, 0);
		//}

		static RouteCollection BuildRoutes (PublicCompany company, City [] StartCities, bool MustContainToken, bool LimitStops, int stops)
		{
			/*
			 * start with empty route collection 
			 * for each start city 
			 * 	for each TrackSegment in that hex containing that city 
			 * 		create a new Route 
			 * 		set city as start city 
			 * 		first track segment = this track segment (city-first direction) 
			 * 		Discard = false; 
			 * 		NotDone = true; 
			 * 		do 
			 * 			if at city 
			 * 			else 
			 * 		while (NotDone) 
			 * 		if (! Discard) 
			 * 			if (MustHaveToken && (! Route.ContainsToken ())) 
			 * 				Discard = true; 
			 * 		if (! Discard) 
			 * 			add route to collection 
			 * return route collection 
			 */

			RouteCollection Routes = new RouteCollection ();

			foreach (City city in StartCities)
			{
				RouteCollection newRoutes = BuildRoutesFromCity (city, company, LimitStops, stops);
				Routes.AddRoutes (newRoutes);
			}

			return (Routes);
		}

		static private RouteCollection BuildRoutesFromCity (City city, PublicCompany company, bool LimitStops, int stops)
		{
			/*
			 *	Build routes from city: 
			 *	start at city 
			 *	stops = 1 
			 *	foreach track segment 
			 *		if touching city 
			 *		make copy of track segment, city first 
			 *		in a loop: 
			 *			if segment conflicts with route, exit loop 
			 *			add segment to route 
			 *			if ends at city 
			 *			if not blocked by token 
			 *				build routes from city (ignore route collection and this base route) 
			 *				for every route after first 
			 *					create a copy of base route 
			 *					append new route 
			 *				append first route to main route 
			 *				increment stops 
			 *				if stops == train stops, exit loop 
			 *			else (track segment) 
			 *				follow track segment to next segment 
			 */
			RouteCollection Routes = new RouteCollection ();

			foreach (TrackSegment track in city.Hex.TrackSegments)
			{
				SegmentEndpoint startEndpoint;
				SegmentEndpoint endEndpoint;
				//
				//  Only consider tracks segments that start or end at a city
				//
				if (track.StartsAtCity (city, out startEndpoint, out endEndpoint))
				{
					//
					//  create a starting route with this track segement
					//
					TrackSegment newSegment = new TrackSegment (city.Hex, startEndpoint, endEndpoint);
					Route baseRoute = new Route ();
					baseRoute.AddTrackSegment (newSegment);

					//
					//  recursively follow paths along this route (can add additional routes to the collection)
					//
					BuildDownstreamRoutes(company, Routes, baseRoute, LimitStops, stops - 1);
				}
			}

			return (Routes);
		}

		static private void BuildDownstreamRoutes (PublicCompany company, RouteCollection Routes, Route baseRoute, bool LimitStops, int stops)
		{
			int count = baseRoute.TrackSegments.Length;
			TrackSegment lastTrack = baseRoute.TrackSegments[count - 1];
			SegmentEndpoint startEndpoint;
			SegmentEndpoint endEndpoint;
			if (lastTrack.End.AtCity)
			{
				stops--;
				//
				//  See if we've hit the train size limit, or route is blocked by tokens
				//
				if ( (LimitStops && (stops <= 0)) ||
					(!CanRunThrough(lastTrack.End.City, company)))
				{
					if (baseRoute.ContainsToken (company))
						Routes.Add (baseRoute);
					// else discard the route by not adding it
					return;
				}

				//
				//  Examine all tracks out of this city.  Discard those that already exist in the route.
				//
				foreach (TrackSegment track in lastTrack.End.City.Hex.TrackSegments)
				{
					if (track.StartsAtCity (lastTrack.End.City, out startEndpoint, out endEndpoint) &&
						(! baseRoute.ConflictsWith (track)))
					{
						// abort this track segment if hits an existing city in this route
						if (/*track.End*/endEndpoint.AtCity && baseRoute.ContainsCity (/*track.End*/endEndpoint.City))
							continue;
						//
						//  make a copy of the route, add the segment to it, and finish those routes
						//
						Route newRoute = new Route (baseRoute);
						TrackSegment newSegment = new TrackSegment (lastTrack.Hex, startEndpoint, endEndpoint);
						newRoute.AddTrackSegment (newSegment);
						BuildDownstreamRoutes(company, Routes, newRoute, LimitStops, stops);
					}
				}
			}
			else
			{
				//
				//  Find destination hex; run all incoming segments on this hexside
				//
				string sNextHex = (string) lastTrack.Hex.Neighbors [lastTrack.End.Hexside];
				if (sNextHex != null)
				{
					string hexside = PublicCompany.InverseDirection (lastTrack.End.Hexside);
					GameboardHex destHex = company.Game.GameboardHexes[sNextHex];
					bool FoundOne = false;
					foreach (TrackSegment track in destHex.TrackSegments)
					{
						if (track.StartsAtHexside (hexside, out startEndpoint, out endEndpoint) &&
							(! baseRoute.ConflictsWith (track)))
						{
							// abort this track segment if hits an existing city in this route
							if (endEndpoint.AtCity && baseRoute.ContainsCity (endEndpoint.City))
								continue;
							//
							//  make a copy of the route, add the segment to it, and finish those routes
							//
							FoundOne = true;
							Route newRoute = new Route (baseRoute);
							TrackSegment newSegment = new TrackSegment (destHex, startEndpoint, endEndpoint);
							newRoute.AddTrackSegment (newSegment);
							BuildDownstreamRoutes(company, Routes, newRoute, LimitStops, stops);
						}
					}
					//
					//  hit end of track before full number of stops
					//
					if ((! FoundOne) && (baseRoute.Stops >= 2))
					{
						baseRoute.TruncateToCity ();
						if (baseRoute.ContainsToken(company))
							Routes.Add (baseRoute);
					}
				}
			}
		}

		static public RouteCollection FindBestRoutes(PublicCompany company, TrainCollection Trains)
		{
			/*
			 * best route collection = new empty route collection
			 * if no trains, return empty route collection
			 *
			 * build routes for each train size
			 * for each route in each train size
			 *     build hastable of all conflicting routes in all other train route collections
			 *
			 * select first train
			 * for each route
			 *     create a test route collection
			 *     apply this route to first train
			 *     add route to test collection
			 */
#if DetailedRouteTracing
			Stopwatch watch = new Stopwatch();
			watch.Start();
#endif
			RouteCollection BestRoutes = new RouteCollection();
			//int BestRouteValue = BestRoutes.TotalValue;

			if (Trains.Count == 0)
				goto done;// return (BestRoutes);

			// NEW TESTING
			// Create a hashtable of tracksegments so we don't have to recreate them for every route
//			Dictionary<string, TrackSegment> TrackSegmentTable = GenerateTrackSegmentTable(company);




			City[] AllCities = City.GetAllCities(company);

			// build routes for each train size
			Dictionary<int, RouteCollection> TrainSizeRoutes = new Dictionary<int, RouteCollection>();
			foreach (Train train in Trains)
			{
				int key = train.Stops;
//				if (train.UnlimitedStops)
//					key = -1;		// use 0, and stops should already be 0

				if (!TrainSizeRoutes.ContainsKey(key))
				{
					RouteCollection routeCollection = BuildRoutes(company, AllCities, true, !train.UnlimitedStops, train.Stops);
					TrainSizeRoutes.Add(key, routeCollection);
#if RouteCalculatorSpeedup
					//
					// The route accululation ends up putting each route twice into the collection twice,
					// in opposite orders.  Since the recursive algorithm below sags under the weight of
					// all these routes, cutting the count in half here can yield 4 or 8 times savings later.
					//
					routeCollection.RemoveMirrorRoutes();
#endif // RouteCalculatorSpeedup

#if DetailedRouteTracing
					Trace.WriteLine(string.Format(" >> {0} train: {1} routes", train.Name, routeCollection.Count));
#endif
				}
			}

#if DetailedRouteTracing
			TimeSpan first = watch.Elapsed;
			Trace.WriteLine(" >> time building all routes: " + first.ToString());
#endif


			CalcConfig config = new CalcConfig();
			config.UseBitVectorAlgorithm = true;		// fastest of the algorithms
			config.BuildTestRoutesRecursively = false;	// inline is faster as well (faster than recursive)
			//config.UseTableAlgorithm = Trains.Count > 2;	// table driven is faster for 3 medium trains (6,4,4), slower for 2 longer trains (8,6)

#if DetailedRouteTracing
			if (config.UseBitVectorAlgorithm)
				Trace.WriteLine(" >> choosing bit-vector ANDing algorithm");
			else if (config.UseTableAlgorithm)
				Trace.WriteLine(" >> choosing table-driven algorithm");
			else if (! config.BuildTestRoutesRecursively)
				Trace.WriteLine(" >> choosing inline code algorithm");
			else
				Trace.WriteLine(" >> choosing recursive code algorithm");
#endif // DetailedRouteTracing


#if RouteCalculatorSpeedup
			config.bitArraySize = 0;
			config.RouteConflictTable = null;
			int conflicts = 0;

			if (config.UseBitVectorAlgorithm)
				config.bitArraySize = BuildRouteBitArrays(TrainSizeRoutes);
			else if (config.UseTableAlgorithm)
			{
				// create and fill in the route conflict table
				//byte[,] RouteConflictTable = new byte[nextRouteId,nextRouteId];
				//for (int i = 0; i < TrainSizeRoutes.Count; i++)
				//{
				//    RouteCollection source = TrainSizeRoutes[trainStops[i]];
				//    for (int j = i; j < TrainSizeRoutes.Count; j++)
				//    {
				//        RouteCollection dest = TrainSizeRoutes[trainStops[j]];
				//        foreach (Route r1 in source)
				//            foreach (Route r2 in dest)
				//            {
				//                if (RouteConflictTable[r1.id,r2.id] == 0)
				//                {
				//                    if (r1.ConflictsWith(r2))
				//                    {
				//                        RouteConflictTable[r1.id,r2.id] = 1;
				//                        RouteConflictTable[r2.id,r1.id] = 1;
				//                        conflicts += 2;
				//                    }
				//                }
				//            }
				//    }
				//}

				// set each route's unique id
				int nextRouteId = 0;
				foreach (RouteCollection coll in TrainSizeRoutes.Values)
					foreach (Route r in coll)
						r.id = nextRouteId++;

	#if DetailedRouteTracing
				Trace.WriteLine(" >> allocating conflict table, size = " + nextRouteId * nextRouteId);
	#endif

				int[] trainStops = new int[TrainSizeRoutes.Count];
				int index = 0;
				foreach (int key in TrainSizeRoutes.Keys)
					trainStops[index++] = key;

				config.RouteConflictTable = new BitArray[nextRouteId];
				for (int i = 0; i < TrainSizeRoutes.Count; i++)
				{
					RouteCollection source = TrainSizeRoutes[trainStops[i]];
					for (int j = i; j < TrainSizeRoutes.Count; j++)
					{
						RouteCollection dest = TrainSizeRoutes[trainStops[j]];
						foreach (Route r1 in source)
							foreach (Route r2 in dest)
							{
								if (config.RouteConflictTable[r1.id] == null)
									config.RouteConflictTable[r1.id] = new BitArray(nextRouteId);
								if (config.RouteConflictTable[r2.id] == null)
									config.RouteConflictTable[r2.id] = new BitArray(nextRouteId);

								if (!config.RouteConflictTable[r1.id][r2.id])
								{
									//if (r1.ConflictsWith(r2))
									if (r1.InlinedConflictsWith(r2))
									{
										config.RouteConflictTable[r1.id][r2.id] = true;
										config.RouteConflictTable[r2.id][r1.id] = true;
										conflicts += 2;
									}
								}
							}
					}
				}

	#if DetailedRouteTracing
				first = watch.Elapsed.Subtract(first);
				Trace.WriteLine(" >> time precomputing conflict table: " + first.ToString());
				Trace.WriteLine(" >> route conflicts found = " + conflicts);
	#endif
			}
#endif // RouteCalculatorSpeedup

			// sort the trains longest-first - needed for proper route collision handling
			TrainCollection OrderedTrains = new TrainCollection(Trains);
			OrderedTrains.SortHighestToLowest();

			//
			// build test route collections and see which is best
			//
			if (config.BuildTestRoutesRecursively)
			{
				// recursive method
				BestRoutes = BuildTestRoutesRecursively(OrderedTrains, TrainSizeRoutes, config);
			}
			else
			{
				// this version unrolls and inlines the recursion
				BestRoutes = BuildTestRoutesInlined(OrderedTrains, TrainSizeRoutes, config);
			}

		done:
#if DetailedRouteTracing
			watch.Stop();
			Trace.WriteLine(" >> FindBestRoutes duration " + watch.Elapsed.ToString());
#endif
			return (BestRoutes);
		}

		/// <summary>
		/// describes HOW to calculate best routes (which algorithm and associated info)
		/// </summary>
		private class CalcConfig
		{
			// bit vector algorithm config
			public bool UseBitVectorAlgorithm;
			public int bitArraySize;	// requires all route.TrackSegmentBitArray's to be created

			// table-driven algorithm config
			public bool UseTableAlgorithm;
			public BitArray[] RouteConflictTable;

			// if none of the above flags is set, use the basic object-comparison algorithm

			// default to the recursive method, but set this to false to run the inlined method
			// (applied to all three variants from above)
			public bool BuildTestRoutesRecursively = true;
		}

		static private RouteCollection BuildTestRoutesRecursively(TrainCollection Trains, Dictionary<int, RouteCollection> TrainSizeRoutes, CalcConfig config)
		{
			long count = 0;
			RouteCollection.callstoBuildTestRoutesRecursively = 0;
			RouteCollection BestRoutes = new RouteCollection();

			Train BaseTrain = Trains[0];
			RouteCollection BaseRoutes = TrainSizeRoutes[BaseTrain.Stops];
			foreach (Route BaseRoute in BaseRoutes)
			{
				RouteCollection TestRoutes = new RouteCollection();
				TestRoutes.Add(BaseRoute);
				TestRoutes.CachedTotalValue = BaseRoute.CachedValue;

				if (Trains.Count > 1)
					BuildTestRoutesRecursively(ref TestRoutes, Trains, 1, TrainSizeRoutes, config);

				if (TestRoutes.CachedTotalValue > BestRoutes.CachedTotalValue)
					BestRoutes = TestRoutes;
				count++;
			}
#if DetailedRouteTracing
			Trace.WriteLine(string.Format(" >> {0} total route collections evaluated (at top level)", count));
			//
			// JoeB: calls to BuildTestRoutesRecursively is a critical performance indicator, and it
			// jumps geometrically with each additional train a railroad has.
			//		1 train, 0 calls
			//		2 trains, N calls, where N is the number of routes in the 2nd train's collection
			//		3 trains, N x M calls, where M is the number of routes in the 3rd trains collection
			Trace.WriteLine(string.Format(" >> {0} total calls to BuildTestRoutesRecursively", RouteCollection.callstoBuildTestRoutesRecursively));
#endif
			return (BestRoutes);
		}

		static private long callstoBuildTestRoutesRecursively;
		static private void BuildTestRoutesRecursively(ref RouteCollection TestRoutes, TrainCollection Trains, int FirstTrain, Dictionary<int, RouteCollection> TrainSizeRoutes, CalcConfig config)
		{
			RouteCollection.callstoBuildTestRoutesRecursively++;
			// Save a copy of the original route collection (we WILL be modifying TestRoutes)
			RouteCollection origRoutes = new RouteCollection (TestRoutes);
			origRoutes.CachedTotalValue = TestRoutes.CachedTotalValue;

			Train thisTrain = Trains[FirstTrain];
			RouteCollection thisRoutes = (RouteCollection) TrainSizeRoutes[thisTrain.Stops];
			bool AddThisRoute;

			foreach (Route route in thisRoutes)
			{
				// Do we add this route?
				//AddThisRoute = !route.ConflictsWith(origRoutes);
				//AddThisRoute = !OptimizedConflictsWith(origRoutes, route);	// SLOWER!
				if (config.UseBitVectorAlgorithm)
					AddThisRoute = !BitVectorConflictsWith(route, origRoutes, config.bitArraySize);
				else if (config.UseTableAlgorithm)
					AddThisRoute = !TableDrivenConflictsWith(route, origRoutes, config.RouteConflictTable);
				else
					AddThisRoute = !route.InlinedConflictsWith(origRoutes);

				if (AddThisRoute)
				{
					RouteCollection bestRoutes = new RouteCollection(origRoutes);	// make a copy
					bestRoutes.Add(route);
					bestRoutes.CachedTotalValue = origRoutes.CachedTotalValue + route.CachedValue;

					if (FirstTrain + 1 < Trains.Count)
						BuildTestRoutesRecursively(ref bestRoutes, Trains, FirstTrain + 1, TrainSizeRoutes, config);

					if (bestRoutes.CachedTotalValue > TestRoutes.CachedTotalValue)
						TestRoutes = bestRoutes;
				}
			}
		}

		static private RouteCollection BuildTestRoutesInlined(TrainCollection Trains, Dictionary<int, RouteCollection> TrainSizeRoutes, CalcConfig config)
		{
			long nEval = 0;
			long nValid = 0;
			long nAdded = 0;
			long nBetter = 0;
			bool AddThisRoute;

#if TESTING
			//
			//  This is a stripped down version of what's happening below.
			//  It takes 10 seconds, compared to 28 seconds for the real code,
			//  and this test version doesn't allocate any route collections.
			//
			//  We're also skimping and using a single 64-bit ulong instead of an array, so it's faster
			//  than the more general algorithm. (Although we're not accumulating OR'ed results)
			//
			//  So 10 seconds seems to be the theoretical max speed for this NxMxP conflict detection algorithm.
			//
			Stopwatch xx = new Stopwatch();
			xx.Start();
			List<ulong[]> bits = new List<ulong[]>();
			for (int train = 0; train < Trains.Count; train++)
			{
				Train ThisTrain = Trains[train];
				RouteCollection ThisTrainRoutes = TrainSizeRoutes[ThisTrain.Stops];
				bits.Add(new ulong[ThisTrainRoutes.Count]);
				for (int i = 0; i < ThisTrainRoutes.Count; i++)
					bits[train][i] = ThisTrainRoutes[i].TrackSegmentBitArray[0];
			}
			Trace.WriteLine(" >> TEST part 1 " + xx.Elapsed.ToString());
			long nTest = 0;
			for (int a = 0; a < bits[0].Length; a++)
			{
				ulong aa = bits[0][a];
				for (int b = 0; b < bits[1].Length; b++)
				{
					ulong bb = aa;
					//if (!AndBits(ref bb, bits[1][b]))
					if ((bb & bits[1][b]) == 0)
					{
						for (int c = 0; c < bits[2].Length; c++)
						{
							ulong cc = bb;
							//if (!AndBits(ref cc, bits[2][c]))
							if ((cc & bits[2][c]) == 0)
							{
								nTest++;
								// also would need to allcoate a route collection here
							}
						}
					}
				}
			}
			xx.Stop();
			Trace.WriteLine(" >> TEST ran for " + xx.Elapsed.ToString());
			Trace.WriteLine(" >> TEST found: " + nTest);
#endif

#if DetailedRouteTracing
			Stopwatch watch = new Stopwatch();
			watch.Start();
#endif

			List<RouteCollection> RouteCombinations = new List<RouteCollection>();
			RouteCollection dummy = new RouteCollection();
			dummy.CachedTotalValue = 0;
			dummy.ORedRouteBitArray = 
#if UseSingle64Bit
				0;
#elif Use64BitArray
				new ulong[(config.bitArraySize + 63) / 64];
#else
				new int[(config.bitArraySize + 31) / 32];
#endif

			RouteCombinations.Add(dummy);
			RouteCollection BestRoutes = dummy;

			for (int train = 0; train < Trains.Count; train++)
			{
				bool OnLastTrain = (train == Trains.Count - 1);
				Train ThisTrain = Trains[train];
				RouteCollection ThisTrainRoutes = TrainSizeRoutes[ThisTrain.Stops];

				// try combing this train's route collections with the saved valid combinations from previous trains
				int lastValidCombination = RouteCombinations.Count;	// needed because we'll be adding more
				for (int valid=0; valid < lastValidCombination; valid++)
				{
					RouteCollection validCombination = RouteCombinations[valid];
					foreach (Route route in ThisTrainRoutes)
					{
						nEval++;

						if (config.UseBitVectorAlgorithm)
						{
							//AddThisRoute = !BitVectorConflictsWith(route, validCombination, config.bitArraySize);
							// try it inlined
							AddThisRoute = true;
#if old_way
							foreach (Route test in validCombination)
							{
								if (AndBits(route.TrackSegmentBitArray, test.TrackSegmentBitArray))
								{
									AddThisRoute = false;
									break;
								}
							}
#else
							// only need to examine the collection's combined route segment bits
							//if (AndBits(validCombination.ORedRouteBitArray, route.TrackSegmentBitArray))
							//	AddThisRoute = false;
							// inline the AndBits
	#if UseSingle64Bit
							if ((validCombination.ORedRouteBitArray & route.TrackSegmentBitArray) != 0)
								AddThisRoute = false;
	#else
							for (int i = 0; i < validCombination.ORedRouteBitArray.Length; i++)
							{
								if ((validCombination.ORedRouteBitArray[i] & route.TrackSegmentBitArray[i]) != 0)
								{
									AddThisRoute = false;
									break;
								}
							}
	#endif
#endif
						}
						else if (config.UseTableAlgorithm)
							AddThisRoute = !TableDrivenConflictsWith(route, validCombination, config.RouteConflictTable);
						else
							AddThisRoute = !route.InlinedConflictsWith(validCombination);

						if (AddThisRoute)
						{
							nValid++;

							// Special - If we're on the last train, we don't need to add this new combination
							// to the route collection list.  But we still need to save it if it's the best
							// route collection so far.
							bool BetterCombination =
								(validCombination.CachedTotalValue + route.CachedValue > BestRoutes.CachedTotalValue);

							if (BetterCombination || (!OnLastTrain))
							{
								RouteCollection newCombination = new RouteCollection(validCombination);	// make a copy
								newCombination.ORedRouteBitArray =
#if UseSingle64Bit
									validCombination.ORedRouteBitArray;
#else
	#if Use64BitArray
									new ulong[validCombination.ORedRouteBitArray.Length];
	#else
									new int[validCombination.ORedRouteBitArray.Length];
	#endif
								for (int i=0; i < validCombination.ORedRouteBitArray.Length; i++)
									newCombination.ORedRouteBitArray[i] = validCombination.ORedRouteBitArray[i];
#endif
								newCombination.Add(route);
								newCombination.CachedTotalValue = validCombination.CachedTotalValue + route.CachedValue;
								// produce a Collection specific bit mask
								OrBits(ref newCombination.ORedRouteBitArray, route.TrackSegmentBitArray);
								// inline the OrBits - is SLOWER for some reason!
								//for (int i = 0; i < newCombination.ORedRouteBitArray.Length; i++)
								//	newCombination.ORedRouteBitArray[i] |= route.TrackSegmentBitArray[i];

								if (BetterCombination)
								{
									nBetter++;
									BestRoutes = newCombination;
								}
								if (!OnLastTrain)
								{
									nAdded++;
									RouteCombinations.Add(newCombination);
								}
							}
						}
					}
				}
			}

#if DetailedRouteTracing
			watch.Stop();
			Trace.WriteLine(" >> BuildTestRoutesInlined ran for " + watch.Elapsed.ToString());
			Trace.WriteLine(" >> total route collections evaluated: " + nEval);
			Trace.WriteLine(" >> valid route combinations found: " + nValid);
			Trace.WriteLine(" >> 'better' route combinations found: " + nBetter);
			Trace.WriteLine(" >> route combinations added to collection: " + nAdded);
#endif
			return (BestRoutes);
		}

#if RouteCalculatorSpeedup
		static private int BuildRouteBitArrays(Dictionary<int, RouteCollection> TrainSizeRoutes)
		{
			Dictionary<string, int> TrackSegmentHash = new Dictionary<string, int>();
			int hexSideId = 0;
	#if DetailedRouteTracing
			Stopwatch watch = new Stopwatch();
			watch.Start();
	#endif // DetailedRouteTracing

			// generate the hexside hash table
			foreach (RouteCollection collection in TrainSizeRoutes.Values)
			{
				foreach (Route route in collection)
				{
					foreach (TrackSegment ts in route.TrackSegments)
					{
						if (!ts.Start.AtCity)
							AddHexsideHash(TrackSegmentHash, ts.Hex, ts.Start, ref hexSideId);
						if (!ts.End.AtCity)
							AddHexsideHash(TrackSegmentHash, ts.Hex, ts.End, ref hexSideId);
					}
				}
			}
			// build each route's bit vector (with one bit for each unique hexside)
#if UseSingle64Bit
			if (hexSideId > 64)
				throw new Exception("number of bits is > 64: " + hexSideId.ToString());
#else
	#if Use64BitArray
			int numInts = (hexSideId + 63) / 64;
	#else
			int numInts = (hexSideId + 31) / 32;
	#endif
#endif
			foreach (RouteCollection collection in TrainSizeRoutes.Values)
			{
				foreach (Route route in collection)
				{
					// create the bit array
					//route.TrackSegmentBitArray = new BitArray(hexSideId/*number of bits*/);
					route.TrackSegmentBitArray =
#if UseSingle64Bit
						0;
#elif Use64BitArray
						new ulong[numInts];
#else
						new int[numInts];
#endif

					// fill it in from the track segments
					foreach (TrackSegment ts in route.TrackSegments)
					{
						if (!ts.Start.AtCity)
							SetBit(ref route.TrackSegmentBitArray, ts.Start.HexsideId);	//route.TrackSegmentBitArray[ts.Start.HexsideId] = true;
						if (!ts.End.AtCity)
							SetBit(ref route.TrackSegmentBitArray, ts.End.HexsideId);	//route.TrackSegmentBitArray[ts.End.HexsideId] = true;
					}
				}
			}

	#if DetailedRouteTracing
			watch.Stop();
			Trace.WriteLine(" >> BuildRouteBitArrays duration " + watch.Elapsed.ToString() +
				", bit vector size = " + hexSideId);
	#endif // DetailedRouteTracing

			return hexSideId;	// number of bits
		}

		static private void AddHexsideHash(Dictionary<string, int> TrackSegmentHash, GameboardHex hex, SegmentEndpoint ep, ref int hexSideId)
		{
			//hash = hex.Location + ep.Hexside;
			string sNextHex = (string)hex.Neighbors[ep.Hexside];
			string hash = hex.Location + sNextHex;

			if (TrackSegmentHash.ContainsKey(hash))
				ep.HexsideId = TrackSegmentHash[hash];
			else
			{
				ep.HexsideId = hexSideId;
				TrackSegmentHash.Add(hash, hexSideId);

				// also need the reverse hex-to-hex hash
				string reversehash = sNextHex + hex.Location;
				TrackSegmentHash.Add(reversehash, hexSideId);

				hexSideId++;
			}
		}

		static private void SetBit(ref int[] array, int bitnum)
		{
			int index = bitnum >> 5;
			bitnum &= 0x1f;
			array[index] |= 1 << bitnum;
		}
		static private void SetBit(ref ulong[] array, int bitnum)
		{
			int index = bitnum >> 6;
			bitnum &= 0x3f;
			array[index] |= ((ulong) 1) << bitnum;
		}
		static private void SetBit(ref ulong bits, int bitnum)
		{
			int index = bitnum >> 6;
			bitnum &= 0x3f;
			bits |= ((ulong)1) << bitnum;
		}

		// return true if result is non-zero
		static private bool AndBits(ref int[] array1, int[] array2)
		{
			// assumes arrays are same size
			for (int i = 0; i < array1.Length; i++)
			{
				if ((array1[i] & array2[i]) != 0)
					return true;
			}
			return false;
		}
		static private bool AndBits(ref ulong[] array1, ulong[] array2)
		{
			// assumes arrays are same size
			for (int i = 0; i < array1.Length; i++)
			{
				if ((array1[i] & array2[i]) != 0)
					return true;
			}
			return false;
		}
		static private bool AndBits(ref ulong bits1, ulong bits2)
		{
			return ((bits1 & bits2) != 0);
		}

		// OR the bits into array1 (modifies array1)
		static private void OrBits(ref int[] array1, int[] array2)
		{
			// assumes arrays are same size
			for (int i = 0; i < array1.Length; i++)
				array1[i] |= array2[i];
		}
		static private void OrBits(ref ulong[] array1, ulong[] array2)
		{
			// assumes arrays are same size
			for (int i = 0; i < array1.Length; i++)
				array1[i] |= array2[i];
		}
		static private void OrBits(ref ulong bits1, ulong bits2)
		{
			bits1 |= bits2;
		}

		static private bool BitVectorConflictsWith(Route route, RouteCollection collection, int bitArraySize)
		{
			//int numints = (bitArraySize + 31) / 32;
			//int[] results = new int[numints];

			foreach (Route test in collection)
			{
				// there's no easy way to test every bit in Anded, so copy to an int array we CAN test
				//BitArray Anded = route.TrackSegmentBitArray.And(test.TrackSegmentBitArray);
				//Anded.CopyTo(results,0);
				//foreach (int i in results)
				//    if (i != 0)
				//        return true;

				if (AndBits(ref route.TrackSegmentBitArray, test.TrackSegmentBitArray))
					return true;
			}
			return false;
		}

		static private bool	TableDrivenConflictsWith(Route route, RouteCollection collection, /*byte[,]*/BitArray[] RouteConflictTable)
		{
			foreach (Route r in collection)
				//if (RouteConflictTable[route.id, r.id] != 0)
				if (RouteConflictTable[route.id][r.id])
					return true;	// these routes conflict
			return false;
		}

		/// <summary>
		/// An optimized version of Route.ConflictsWith(RouteCollection)
		/// 
		/// THIS FUNCTION REQUIRES THE Route.OverlapPointHashList TO BE FILLED IN
		/// </summary>
		/// <param name="origRoutes"></param>
		/// <param name="route"></param>
		/// <returns>true if 'route' conflicts with 'collection', false if no conflict</returns>
		static private bool OptimizedConflictsWith(RouteCollection collection, Route route)
		{
			foreach (Route test in collection)
			{
				foreach (string overlap in test.OverlapPointHashList)
				{
					if (route.OverlapPointHashList.Contains(overlap))
						return true;	// conflicts
				}
			}
			return false;
		}
#endif // RouteCalculatorSpeedup

		//static private bool RouteConflictsWithCollection(Dictionary<Route, List<Route>> ConflictingRoutes, RouteCollection collection, Route route)
		//{
		//    foreach (Route r in collection)
		//    {
		//        if (ConflictingRoutes[route].Contains(r))
		//            return true;
		//    }
		//    return false;
		//}

		/// <summary>
		/// Return true if the city is not tokened up, or the company has a token here
		/// </summary>
		/// <param name="city"></param>
		/// <param name="company"></param>
		/// <returns></returns>
		static bool CanRunThrough(City city, PublicCompany company)
		{
			if (city.Offboard)
				return false;

			if (city.TokenSpots < 1)	// non-tokenable town never blocks
				return true;

			if (city.Tokens < city.TokenSpots)
				return true;

			foreach (Token token in city.Hex.Tokens)
			{
				// this company's token?
				if (token.Company == company)
				{
					if (! city.Hex.SeperateCities)
						return true;
					// if a multi-city tile, make sure token in this city
					if (city.HexsidesConnectsTo.Contains(token.LocationInHex.Compass))
						return true;
				}
			}
			return false;
		}

#if RouteCalculatorSpeedup
		/// <summary>
		/// Find routes that are exact mirror images of each other, and remove one of them from the collection.
		/// </summary>
		protected void RemoveMirrorRoutes()
		{
//#if DetailedRouteTracing
//			Trace.WriteLine(" >> RemoveMirrorRoutes start");
//#endif
			List<Route> removeList = new List<Route>();
			long count = 0;
	#if too_slow
			foreach (Route route in this)
			{
				foreach (Route test in this)
				{
					count++;
					if ((test != route) &&
						(!removeList.Contains(route)) &&
						(!removeList.Contains(test)) &&
						RouteCollection.AreMirrorRoutes(route, test))
					{
						removeList.Add(test);
						break;	// break here relies on only ONE potential mirror route in the collection
					}
				}
			}
	#else
			// build the hashtable, and at the same time discard mirror routes as they're found
			Dictionary<string, Route> routeHash = new Dictionary<string, Route>();
			foreach (Route route in this)
			{
				count++;
				string forward = route.GetRouteHash();
				string reverse = route.GetReverseRouteHash();

				if (routeHash.ContainsKey(forward) || routeHash.ContainsKey(reverse))
					removeList.Add(route);
				else
				{
					routeHash[forward] = route;
					routeHash[reverse] = route;

					// cache some values for faster routine combining
					route.CachedValue = route.Value;
					ComputeRouteOverlapPoints (route);
				}
			}
	#endif
			foreach (Route route in removeList)
				this.Remove(route);

//#if DetailedRouteTracing
//			Trace.WriteLine(" >> RemoveMirrorRoutes stop");
//#endif
		}
#endif // RouteCalculatorSpeedup

#if RouteCalculatorSpeedup
		static private void ComputeRouteOverlapPoints(Route route)
		{
			route.OverlapPointHashList = new List<string>();
			foreach (TrackSegment ts in route.TrackSegments)
				AddTrackSegmentHashes(route.OverlapPointHashList, ts);
		}

		static private void AddTrackSegmentHashes(List<string> hashList, TrackSegment ts)
		{
			// for now we only care about hexside track connections
			// TODO: this doesn't handle city-to-city connections within the same hex (none in 1856)
			if (!ts.Start.AtCity)
			{
				hashList.Add(ts.Hex.Location + " " + ts.Start.Hexside);
				//ts.Start.HexsideInt = HexsideToInt(ts.Start.Hexside);
			}
			if (!ts.End.AtCity)
			{
				hashList.Add(ts.Hex.Location + " " + ts.End.Hexside);
				//ts.End.HexsideInt = HexsideToInt(ts.End.Hexside);
			}
		}

		//static private int HexsideToInt(string Hexside)
		//{
		//    switch (Hexside)
		//    {
		//        case "NW":
		//            return 1;
		//        case "N":
		//            return 2;
		//        case "NE":
		//            return 3;
		//        case "SE":
		//            return 4;
		//        case "S":
		//            return 5;
		//        case "SW":
		//            return 6;
		//        default:
		//            return 0;	// this is an error
		//    }
		//}
#endif // RouteCalculatorSpeedup

#if not_needed
		static protected bool AreMirrorRoutes(Route r1, Route r2)
		{
			if (r1.TrackSegments.Length != r2.TrackSegments.Length)
				return false;

			// compare routes' track segments in reverse order
			TrackSegment t1, t2;
			int i1 = 0;
			int i2 = r1.TrackSegments.Length-1;

			while (i1 < r1.TrackSegments.Length)
			{
				t1 = r1.TrackSegments[i1++];
				t2 = r2.TrackSegments[i2--];

				if (!t1.IsSameSegment(t2))
					return false;
			}

			return true;
		}
#endif

		//bool CanUseTrackSegement(GameboardHex hex, TrackSegment[] segments)
		//{
		//    return false;	// TEMP
		//}

		//bool CanRunIntoHexOnSide (GameboardHex hex, string side)
		//{
		//    /*
		//    run each route from start to end 
		//    if route contains hex, return (entered from 'side') 
		//        if route ends right before 'hex', from hexside 'side" 
		//            return true 
		//    return false 
		//    */
		//    return false;	// TEMP
		//}
	}

	[Serializable]
	public class Route
	{
		public Route()
		{
		}
		public Route(Route copyFrom)
		{
			Segments = (ArrayList)copyFrom.Segments.Clone();
		}

		public int Value
		{
			get
			{
				int val = 0;
				TrackSegment track;

				for (int i = 0; i < Segments.Count; i++)
				{
					track = (TrackSegment)Segments[i];
					if (track.Start.AtCity)
						val += track.Start.City.Value;
				}

				if (Segments.Count > 0)
				{
					track = (TrackSegment)Segments[Segments.Count - 1];
					if (track.End.AtCity)
						val += track.End.City.Value;
				}

				return val;
			}
		}

		private ArrayList Segments = new ArrayList();
		private TrackSegment[] CachedSegments = null;

		//public List<Route> ConflictingRoutes = null;	// used by route calculator
		public int CachedValue;	// used by route calculator
		public List<string> OverlapPointHashList;	// used by route calculator
		public int id;		// used by route calculator
		//public BitArray TrackSegmentBitArray;	// used by route calculator
#if UseSingle64Bit
		public ulong TrackSegmentBitArray;	// used by route calculator
#elif Use64BitArray
		public ulong[] TrackSegmentBitArray;	// used by route calculator
#else
		public int[] TrackSegmentBitArray;	// used by route calculator
#endif

		public TrackSegment[] TrackSegments
		{
			get
			{
				if (CachedSegments == null)
				{
					CachedSegments = new TrackSegment[Segments.Count];
					for (int i = 0; i < Segments.Count; i++)
						CachedSegments[i] = (TrackSegment)Segments[i];
				}
				return CachedSegments;
			}
		}

		public void AddTrackSegment(TrackSegment ts)
		{
			Segments.Add(ts);
			CachedSegments = null;
		}

		public bool ContainsCity(City city)
		{
			foreach (TrackSegment ts in TrackSegments)
				if (ts.ContainsCity(city))
					return true;
			return false;
		}

		public void TruncateToCity()
		{
			// can't use foreach since it walks the list backwards
			for (int i = Segments.Count - 1; i >= 0; i--)
			{
				if (((TrackSegment)Segments[i]).End.AtCity)
				{
					if (i < Segments.Count - 1)
					{
						Segments.RemoveRange(i + 1, Segments.Count - i - 1);
						CachedSegments = null;
					}
					return;
				}
			}
			Segments.RemoveRange(0, Segments.Count);
			CachedSegments = null;
		}

		public int Stops
		{
			get
			{
				int stops = 0;
				TrackSegment track;

				for (int i = 0; i < Segments.Count; i++)
				{
					track = (TrackSegment)Segments[i];
					if (track.Start.AtCity)
						stops++;
				}

				if (Segments.Count > 0)
				{
					track = (TrackSegment)Segments[Segments.Count - 1];
					if (track.End.AtCity)
						stops++;
				}

				return (stops);
			}
		}

		public override string ToString()
		{
			StringBuilder sb = new StringBuilder();
			ToString(sb);
			return sb.ToString();
		}

		public void ToString(StringBuilder sb)
		{
			sb.AppendFormat("{0} route({1}): ", Stops, Value);
			// could use GetRouteHash (for now), but we'll keep separate because this should always be user readable
			for (int i = 0; i < TrackSegments.Length; i++)
			{
				if (i > 0)
					sb.Append(", ");
				TrackSegments[i].ToString(sb);
			}
		}

		public void ToStringTerse(StringBuilder sb)
		{
			sb.AppendFormat("{0} route({1}): ", Stops, Value);
			// we'll only describe cities.  The first city in the route is a Start city, but all others will be End cities
			bool bStart = true;
			for (int i = 0; i < TrackSegments.Length; i++)
			{
				if (bStart)
				{
					if (TrackSegments[i].Start.AtCity)
					{
						TrackSegment.ToString(sb, TrackSegments[i].Start);
						bStart = false;
					}
				}
				else
				{
					if (TrackSegments[i].End.AtCity)
					{
						sb.Append(" to ");
						TrackSegment.ToString(sb, TrackSegments[i].End);
					}
				}
			}
		}

		public string GetRouteHash()
		{
			StringBuilder sb = new StringBuilder();
			GetRouteHash(sb);
			return sb.ToString();
		}

		public void GetRouteHash(StringBuilder sb)
		{
			for (int i = 0; i < TrackSegments.Length; i++)
			{
				if (i > 0)
					sb.Append(", ");
				TrackSegments[i].ToString(sb);
			}
		}

		public string GetReverseRouteHash()
		{
			StringBuilder sb = new StringBuilder();
			GetReverseRouteHash(sb);
			return sb.ToString();
		}

		public void GetReverseRouteHash(StringBuilder sb)
		{
			for (int i = TrackSegments.Length - 1; i >= 0; i--)
			{
				if (i < TrackSegments.Length - 1)
					sb.Append(", ");
				TrackSegments[i].ReverseToString(sb);
			}
		}

		public bool ContainsToken(PublicCompany company)
		{
			// can't use foreach since it walks the list backwards
			for (int i = 0; i < TrackSegments.Length; i++)
			{
				TrackSegment ts = TrackSegments[i];
				if (ts.Start.AtCity)
				{
					foreach (Token token in ts.Hex.Tokens)
						if (token.Company == company)
						{
							// in cases like Toronto, we need to check whether the token is on the right side
							if (ts.Start.City.Hex.SeperateCities)
							{
								Side side = token.LocationInHex;
								string direction = side.Compass.ToString();
								if (CanTraceTrackToHexside(ts.Hex.TrackSegments, ts.Start, ts.End, direction))
									return true;
							}
							else
								return true;
						}
				}
			}
			// don't need to test every segment end, just the last one
			if (TrackSegments.Length > 0)
			{
				TrackSegment ts = TrackSegments[TrackSegments.Length - 1];
				if (ts.End.AtCity)
					foreach (Token token in ts.Hex.Tokens)
						if (token.Company == company)
						{
							// in cases like Toronto, we need to check whether the token is on the right side
							if (ts.End.City.Hex.SeperateCities)
							{
								Side side = token.LocationInHex;
								string direction = side.Compass.ToString();
								if (CanTraceTrackToHexside(ts.Hex.TrackSegments, ts.Start, ts.End, direction))
									return true;
							}
							else
								return true;
						}
			}
			return false;
		}

		/*
		static private bool CanTraceTrackToHexside (TrackSegment [] Segments, TrackSegment startSegment, string endHexside)
		{
			if ((! startSegment.Start.AtCity) && (startSegment.Start.Hexside == endHexside))
				return true;
			if ((! startSegment.End.AtCity) && (startSegment.End.Hexside == endHexside))
				return true;
			//if (! startSegment.End.AtCity)
			//	return (startSegment.End.Hexside == endHexside);
			if ((! startSegment.End.AtCity) && (startSegment.End.Hexside == endHexside))
				return true;
			for (int i=0; i < Segments.Length; i++)
			{
				TrackSegment ts = Segments[i];
				if (ts != startSegment)
				{
					if (ts.Start.AtCity && startSegment.End.AtCity)
					{
						if ((ts.Start.City == startSegment.End.City) && (! ts.OverlapsWith (startSegment)))
							if (CanTraceTrackToHexside (Segments, ts, endHexside))
								return true;
					}
				}
			}
			return false;
		}
		*/

		static private bool CanTraceTrackToHexside(TrackSegment[] Segments, SegmentEndpoint startPoint, SegmentEndpoint endPoint, string endHexside)
		{
			if ((!startPoint.AtCity) && (startPoint.Hexside == endHexside))
				return true;
			if ((!endPoint.AtCity) && (endPoint.Hexside == endHexside))
				return true;
			//if (! endPoint.AtCity)
			//	return (endPoint.Hexside == endHexside);
			//if ((! endPoint.AtCity) && (endPoint.Hexside == endHexside))
			//	return true;
			City city = (startPoint.AtCity) ? startPoint.City : endPoint.City;
			if (city == null)
				return false;
			for (int i = 0; i < Segments.Length; i++)
			{
				TrackSegment ts = Segments[i];
				SegmentEndpoint newStart, newEnd;
				if (ts.StartsAtCity(city, out newStart, out newEnd))
				{
					if ((newStart != startPoint) && (newStart != endPoint))
					{
						if (newEnd.AtCity)
						{
							if (CanTraceTrackToHexside(Segments, newStart, newEnd, endHexside))
								return true;
						}
						else if (newEnd.Hexside == endHexside)
							return true;
					}
				}
			}
			return false;
		}

		public bool ConflictsWith(TrackSegment track)
		{
			foreach (TrackSegment ts in TrackSegments)
				if (ts.OverlapsWith(track))
					return true;
			return false;
		}

		public bool ConflictsWith(Route route)
		{
			foreach (TrackSegment ts in TrackSegments)
				if (route.ConflictsWith(ts))
					return true;
			return false;
		}

		public Route FindConflictingRoute(RouteCollection routeCollection)
		{
			foreach (Route route in routeCollection)
				if (this.ConflictsWith(route))
					return route;
			return null;
		}

		public bool ConflictsWith(RouteCollection routeCollection)
		{
			return (null != FindConflictingRoute(routeCollection));
		}

#if RouteCalculatorSpeedup
		// try inlining the whole thing
		public bool InlinedConflictsWith(RouteCollection routeCollection)
		{
			foreach (Route route in routeCollection)
			{
				if (InlinedConflictsWith(route))
					return true;
			}
			return false;
		}

		public bool InlinedConflictsWith(Route route)
		{
				foreach (TrackSegment ts in this.TrackSegments)
					foreach (TrackSegment segment in route.TrackSegments)
					{
						//if (ts.OverlapsWith(segment))
						//	return true;

						// this inner logic is copied from TrackSegment.OverlapsWith
						if (ts.Hex == segment.Hex)
						{
							// no city-to-city segments in 1856, so this first if() is never taken in 1856
							if (ts.Start.AtCity && ts.End.AtCity)
							{
								//
								//  If city to city connection, they both have to match (in either order)
								//
								if (segment.Start.AtCity && segment.End.AtCity)
								{
									//if ( (Start.City.Equals (segment.Start.City) && End.City.Equals (segment.End.City)) ||
									//  (Start.City.Equals (segment.End.City) && End.City.Equals (segment.Start.City)))
									if (((ts.Start.City == segment.Start.City) && (ts.End.City == segment.End.City)) ||
										((ts.Start.City == segment.End.City) && (ts.End.City == segment.Start.City)))
										return true;
								}
							}
#if not_unrolled
							else if (!(segment.Start.AtCity && segment.End.AtCity))
							{
								if (!ts.Start.AtCity)
								{
									if (!segment.Start.AtCity)
									{
										//if (Hex.Equals (segment.Hex) && Start.Hexside.Equals (segment.Start.Hexside))
										if (/*(Hex == segment.Hex) &&*/ (ts.Start.Hexside == segment.Start.Hexside))
											return true;
									}
									if (!segment.End.AtCity)
									{
										//if (Hex.Equals (segment.Hex) && Start.Hexside.Equals (segment.End.Hexside))
										if (/*(Hex == segment.Hex) &&*/ (ts.Start.Hexside == segment.End.Hexside))
											return true;
									}
								}
								if (!ts.End.AtCity)
								{
									if (!segment.Start.AtCity)
									{
										//if (Hex.Equals (segment.Hex) && End.Hexside.Equals (segment.Start.Hexside))
										if (/*(Hex == segment.Hex) &&*/ (ts.End.Hexside == segment.Start.Hexside))
											return true;
									}
									if (!segment.End.AtCity)
									{
										//if (Hex.Equals (segment.Hex) && End.Hexside.Equals (segment.End.Hexside))
										if (/*(Hex == segment.Hex) &&*/ (ts.End.Hexside == segment.End.Hexside))
											return true;
									}
								}
							}
#endif // not_unrolled
							// unroll into separate tests to eliminate the duplicate segment.X.AtCity tests
							// (yes, this is ugly and hard to understand now)
							// (and it only saves about 3% in the CGR test - 34.9 vs. 36.4 seconds)
							else
							{
								if (!segment.Start.AtCity)
								{
									if (!ts.Start.AtCity)
									{
										if (ts.Start.Hexside == segment.Start.Hexside)
											return true;
										if (!segment.End.AtCity)
										{
											if (ts.Start.Hexside == segment.End.Hexside)
												return true;
										}
									}
									if (!ts.End.AtCity)
									{
										if (ts.End.Hexside == segment.Start.Hexside)
											return true;
										if (!segment.End.AtCity)
										{
											if (ts.End.Hexside == segment.End.Hexside)
												return true;
										}
									}
								}
								else if (!segment.End.AtCity)
								{
									if (!ts.Start.AtCity)
									{
										if (!segment.Start.AtCity)
										{
											if (ts.Start.Hexside == segment.Start.Hexside)
												return true;
										}
										if (ts.Start.Hexside == segment.End.Hexside)
											return true;
									}
									if (!ts.End.AtCity)
									{
										if (!segment.Start.AtCity)
										{
											if (ts.End.Hexside == segment.Start.Hexside)
												return true;
										}
										if (ts.End.Hexside == segment.End.Hexside)
											return true;
									}
								}
							}
						}
					}
			return false;
		}
#endif // RouteCalculatorSpeedup
	}

	[Serializable]
	public class SegmentEndpoint
	{
		public bool AtCity = false;
		public City City = null;
		public string Hexside = "";

		//public int HexsideInt;	// used by route calculator
		public int HexsideId;	// used by route calculator

		public SegmentEndpoint ()
		{
		}

		public SegmentEndpoint (SegmentEndpoint copy)
		{
			AtCity = copy.AtCity;
			City = copy.City;
			Hexside = copy.Hexside;
		}
	}

	[Serializable]
	public class TrackSegment
	{
		public GameboardHex Hex = null;
		public SegmentEndpoint Start = null;
		public SegmentEndpoint End = null;

		public TrackSegment ()
		{
			Start = new SegmentEndpoint ();
			End = new SegmentEndpoint ();
		}

		public TrackSegment (GameboardHex hex, SegmentEndpoint start, SegmentEndpoint end)
		{
			Hex = hex;
			Start = new SegmentEndpoint (start);
			End = new SegmentEndpoint (end);
		}

		public override string ToString ()
		{
			StringBuilder sb = new StringBuilder ();
			ToString (sb);
			return sb.ToString ();
		}

		public void ToString (StringBuilder sb)
		{
			ToString(sb, Start);
			sb.Append (" to ");
			ToString(sb, End);
		}

		public void ReverseToString(StringBuilder sb)
		{
			ToString(sb, End);
			sb.Append(" to ");
			ToString(sb, Start);
		}

		static public void ToString(StringBuilder sb, SegmentEndpoint point)
		{
			if (point.AtCity)
			{
				if (point.City.Name.Length > 0)
					sb.Append(point.City.Name);
				else if (point.City.Hex.TownType == GameboardHex.eTownType.Town)
					sb.AppendFormat("Town {0}", point.City.Hex.Location);
				else
					sb.AppendFormat("City {0}", point.City.Hex.Location);
				sb.AppendFormat(" ({0})", point.City.Value);
			}
			else
				sb.AppendFormat("{0}", point.Hexside);
		}

		public bool StartsAtCity (City city, out SegmentEndpoint startEndpoint, out SegmentEndpoint endEndpoint)
		{
			bool Use = false;
			startEndpoint = null;
			endEndpoint = null;
			if (Start.AtCity && Start.City.Equals (city))
			{
				Use = true;
				startEndpoint = Start;
				endEndpoint = End;
			}
			else if (End.AtCity && End.City.Equals (city))
			{
				Use = true;
				startEndpoint = End;
				endEndpoint = Start;
			}
			return (Use);
		}

		public bool StartsAtHexside (string direction, out SegmentEndpoint startEndpoint, out SegmentEndpoint endEndpoint)
		{
			bool Use = false;
			startEndpoint = null;
			endEndpoint = null;
			if ((! Start.AtCity) && (Start.Hexside == direction))
			{
				Use = true;
				startEndpoint = Start;
				endEndpoint = End;
			}
			else if ((! End.AtCity) && (End.Hexside == direction))
			{
				Use = true;
				startEndpoint = End;
				endEndpoint = Start;
			}
			return (Use);
		}

		public bool ContainsCity (City city)
		{
			return (Start.AtCity && Start.City.Equals (city)) || (End.AtCity && End.City.Equals (city));
		}

		/// <summary>
		/// Returns true if either end of the track segment hits the same hexside. Use this to prevent
		/// train routes from sharing track.
		/// </summary>
		/// <param name="segment"></param>
		/// <returns></returns>
		public bool OverlapsWith (TrackSegment segment)
		{
			//
			// if (city to city connection) 
			//	 if both cities match (in either order), return true 
			//	 else return false 
			// else 
			//	 if any segment hexside matches any this hexside, return true 
			//	 else return false
			//
			if (Hex != segment.Hex)
				return false;
			if (Start.AtCity && End.AtCity)
			{
				//
				//  If city to city connection, they both have to match (in either order)
				//
				if (segment.Start.AtCity && segment.End.AtCity)
				{
					//if ( (Start.City.Equals (segment.Start.City) && End.City.Equals (segment.End.City)) ||
					//  (Start.City.Equals (segment.End.City) && End.City.Equals (segment.Start.City)))
					if ( ((Start.City == segment.Start.City) && (End.City == segment.End.City)) ||
					  ((Start.City == segment.End.City) && (End.City == segment.Start.City)))
						return true;
				}
			}
			else if (!(segment.Start.AtCity && segment.End.AtCity))
			{
				if (!Start.AtCity)
				{
					if (!segment.Start.AtCity)
					{
						//if (Hex.Equals (segment.Hex) && Start.Hexside.Equals (segment.Start.Hexside))
						if (/*(Hex == segment.Hex) &&*/ (Start.Hexside == segment.Start.Hexside))
							return true;
					}
					if (!segment.End.AtCity)
					{
						//if (Hex.Equals (segment.Hex) && Start.Hexside.Equals (segment.End.Hexside))
						if (/*(Hex == segment.Hex) &&*/ (Start.Hexside == segment.End.Hexside))
							return true;
					}
				}
				if (!End.AtCity)
				{
					if (!segment.Start.AtCity)
					{
						//if (Hex.Equals (segment.Hex) && End.Hexside.Equals (segment.Start.Hexside))
						if (/*(Hex == segment.Hex) &&*/ (End.Hexside == segment.Start.Hexside))
							return true;
					}
					if (!segment.End.AtCity)
					{
						//if (Hex.Equals (segment.Hex) && End.Hexside.Equals (segment.End.Hexside))
						if (/*(Hex == segment.Hex) &&*/ (End.Hexside == segment.End.Hexside))
							return true;
					}
				}
			}
			return false;
		}

		//public bool OverlapsWith (TrackSegment [] segments)
		//{
		//    foreach (TrackSegment ts in segments)
		//        if (this.OverlapsWith (ts))
		//            return true;
		//    return false;
		//}

		/// <summary>
		/// Returns true if the track segments are the same. Use this to prevent adding the same segment
		/// (in either direction) to the same collection twice.
		/// </summary>
		/// <param name="segment"></param>
		/// <returns></returns>
		public bool IsSameSegment(TrackSegment segment)
		{
			bool SameStart = false;
			bool SameEnd = false;
			bool Reverse = false;

			// do they share the same start point?
			if (Start.AtCity)
			{
				if (segment.Start.AtCity && (Start.City == segment.Start.City))
					SameStart = true;
				else if (segment.End.AtCity && (Start.City == segment.End.City))
				{
					Reverse = true;
					SameStart = true;
				}
			}
			else
			{
				if ((! segment.Start.AtCity) && (Start.Hexside == segment.Start.Hexside))
					SameStart = true;
				else if ((! segment.End.AtCity) && (Start.Hexside == segment.End.Hexside))
				{
					Reverse = true;
					SameStart = true;
				}
			}

			// do they share the same end point?
			if (End.AtCity)
			{
				if ((!Reverse) && segment.End.AtCity && (End.City == segment.End.City))
					SameEnd = true;
				else if (Reverse && segment.Start.AtCity && (End.City == segment.Start.City))
					SameEnd = true;
			}
			else
			{
				if ((!Reverse) && (!segment.End.AtCity) && (End.Hexside == segment.End.Hexside))
					SameEnd = true;
				else if (Reverse && (!segment.Start.AtCity) && (End.Hexside == segment.Start.Hexside))
					SameEnd = true;
			}

			return SameStart && SameEnd;
		}

		/// <summary>
		/// Call this function for a hex after placing a new tile there.
		/// </summary>
		/// <param name="hex">Writes the hex.Cities and hex.TrackSegments members</param>
		static public void CalculateHexRoutes (GameboardHex hex)
		{
			City city;
			ArrayList Segments = new ArrayList ();

			if (hex.HexType == GameboardHex.eHexType.OffBoard)
			{
				hex.Cities = new City [1];
				city = new City ();
				city.Hex = hex;
				city.Offboard = true;
				city.Name = MakeCityName(hex);
				//city.Tokens = hex.Tokens.Count;
				//city.TokenSpots = CalcCityTokens(hex);
				//city.Value = hex.Value;
				hex.Cities[0] = city;

				foreach (string side in hex.Neighbors.Keys)
				{
					TrackSegment ts = new TrackSegment ();
					ts.Hex = hex;
					ts.Start.AtCity = true;
					ts.Start.City = city;

					ts.End.AtCity = false;
					ts.End.Hexside = side;

					if (!SameSegmentInCollection(ts, Segments))
						Segments.Add (ts);
				}
			}
			else
			{
				//
				// create cities
				//
				int citycount = 0;
				if (hex.TownType != GameboardHex.eTownType.None)
				{
					// eTownType.Town = 1 town
					// eTownType.DblTown = 2 towns
					// eTownType.City && (! SeperateCities) = 1 city
					// eTownType.City && SeperateCities = 2 cities
					string whichCity = null;
					citycount = (hex.TownType == GameboardHex.eTownType.DblTown) ? 2 : 1;
					if ((citycount == 1) && hex.SeperateCities)
						citycount = 2;
					if (citycount == 2)
						whichCity = " A";

					hex.Cities = new City [citycount];

					// create the (first) city for this hex
					city = new City ();
					city.Hex = hex;
					city.Name = MakeCityName(hex, whichCity);
					//city.Tokens = hex.Tokens.Count;
					//city.TokenSpots = CalcCityTokens(hex);
					//city.Value = hex.Value;
					hex.Cities[0] = city;

					if (citycount == 2)
					{
						// create the second city for this hex
						city = new City ();
						city.Hex = hex;
						whichCity = " B";
						city.Name = MakeCityName(hex, whichCity);
						//city.Tokens = hex.Tokens.Count;
						//city.TokenSpots = CalcCityTokens(hex);
						//city.Value = hex.Value;
						hex.Cities[1] = city;
					}
				}

				//
				// connect hexsides to cities or other hexsides
				//
				//int citynum = 0;
				//int segmentNum = 0;
				foreach (Side startSide in hex.ExistingRoutes.Keys)
				{
					SideCollection endSides = hex.ExistingRoutes [startSide] as SideCollection;

					if (endSides.Count == 0)
					{
						// track goes from side to city, eg. yellow Toronto starting tile
						TrackSegment ts = new TrackSegment ();
						ts.Hex = hex;
						ts.Start.AtCity = false;
						ts.Start.Hexside = startSide.GetDirection ();

						ts.End.AtCity = true;
						ts.End.City = /*hex.Cities[citynum];*/ WhichCityDoesHexsideConnectTo(hex, startSide, null);

						//FixCityName (hex.Cities[citynum], ts.Start.Hexside);

						if (!SameSegmentInCollection(ts, Segments))
							Segments.Add (ts);

						//if (citynum < citycount - 1)
						//	citynum++;
					}
					else
					{
						//citynum = 0;
						foreach (Side side in endSides)
						{
							TrackSegment ts = new TrackSegment ();
							ts.Hex = hex;
							ts.Start.AtCity = false;
							ts.Start.Hexside = startSide.GetDirection ();

							if (hex.TownType == GameboardHex.eTownType.None)
							{
								ts.End.AtCity = false;
								ts.End.Hexside = side.GetDirection ();

								if (!SameSegmentInCollection(ts, Segments))
									Segments.Add (ts);
							}
							else
							{
								ts.End.AtCity = true;
								ts.End.City = /*hex.Cities[citynum];*/ WhichCityDoesHexsideConnectTo(hex, startSide, side);

								//FixCityName (hex.Cities[citynum], ts.Start.Hexside);

								if (!SameSegmentInCollection(ts, Segments))
									Segments.Add (ts);

								ts = new TrackSegment ();
								ts.Hex = hex;
								ts.Start.AtCity = true;
								ts.Start.City = /*hex.Cities[citynum];*/ WhichCityDoesHexsideConnectTo(hex, side, startSide);

								ts.End.AtCity = false;
								ts.End.Hexside = side.GetDirection ();

								//FixCityName (hex.Cities[citynum], ts.End.Hexside);

								if (!SameSegmentInCollection(ts, Segments))
									Segments.Add (ts);

								// JoeB NOTE: Double-town tiles will not work right unless
								// the "same-city" segments are next to each other in the list.
								// DO NOT MIX THEM.
								//if (++segmentNum == 2)
								//{
								//	segmentNum = 0;
								//	if (citynum < hex.Cities.Length - 1)
								//		citynum++;
								//}
							}
						}
					}
				}
			}

			//hex.TrackSegments = new TrackSegment[Segments.Count];
			//for (int i=0; i < Segments.Count; i++)
			//	hex.TrackSegments[i] = (TrackSegment) Segments [i];
			hex.TrackSegments = (TrackSegment[]) Segments.ToArray(typeof(TrackSegment));
		}

		static private City WhichCityDoesHexsideConnectTo(GameboardHex hex, Side thisSide, Side destSide)
		{
			// find the city that already connects to this hexside
			City firstNullCity = null;
			foreach (City testCity in hex.Cities)
			{
				if ((testCity.HexsidesConnectsTo.Count == 0) && (firstNullCity == null))
					firstNullCity = testCity;
				foreach (Side.CompassDirection testSide in testCity.HexsidesConnectsTo)
				{
					if (testSide == thisSide.Compass)
						return testCity;
					if ((destSide != null) && (testSide == destSide.Compass))
					{
						if (!testCity.HexsidesConnectsTo.Contains(thisSide.Compass))
							testCity.HexsidesConnectsTo.Add(thisSide.Compass);
						return testCity;
					}
				}
			}

			// if none found, add it to the first city with no hexside connections
			if (firstNullCity != null)
			{
				firstNullCity.HexsidesConnectsTo.Add(thisSide.Compass);
				return firstNullCity;
			}

			// if still none found, just make it the first city
			City city = hex.Cities[0];
			city.HexsidesConnectsTo.Add(thisSide.Compass);
			return city;
		}

		static private string MakeCityName(GameboardHex hex)
		{
			return MakeCityName(hex, null);
		}

		static private string MakeCityName(GameboardHex hex, string whichCity)
		{
			if (hex.City.Length > 0)
				return hex.City + whichCity;
			if (hex.TownType == GameboardHex.eTownType.City)
				return string.Format("City{0} {1}", whichCity, hex.Location);
			return string.Format("Town{0} {1}", whichCity, hex.Location);
		}

		//static private void FixCityName (City city, string hexside)
		//{
		//    int len = city.Name.Length;
		//    if (len > 0)
		//    {
		//        if (city.Name[len-1] == '%')
		//            city.Name = city.Name.Substring (0, len - 1) + hexside;
		//    }
		//}

		// JoeB: Used to be called ConflictingSegmentInCollection, but that would incorrectly reject multiple
		// track segments in a green or brown tile that share one endpoint but not the other.  We still need
		// to check for duplciate segments because
		//static private bool ConflictingSegmentInCollection(TrackSegment ts, ArrayList Segments)
		//{
		//    foreach (TrackSegment track in Segments)
		//        if (ts.OverlapsWith (track))
		//            return true;
		//    return false;
		//}
		static private bool SameSegmentInCollection(TrackSegment ts, ArrayList Segments)
		{
			foreach (TrackSegment track in Segments)
				if (ts.IsSameSegment(track))
					return true;
			return false;
		}

		static public TrackSegment [] GetNonMatchingTrackSegments (TrackSegment [] originalSegments, TrackSegment [] newSegments)
		{
			// returns those segements in newSegments that are not in originalSegments 
			ArrayList list = new ArrayList ();

			foreach (TrackSegment test in newSegments)
			{
				bool InOrig = false;
				foreach (TrackSegment orig in originalSegments)
				{
					if (orig == test)
					{
						InOrig = true;
						break;
					}
				}
				if (! InOrig)
					list.Add (test);
			}

			TrackSegment [] NonMatching = new TrackSegment [list.Count];
			for (int i=0; i < list.Count; i++)
				NonMatching[i] = (TrackSegment) list[i];
			return NonMatching;
		}
	}

	[Serializable]
	public class City
	{
		public GameboardHex Hex = null;
		public string Name;
		public bool Offboard = false;
		//private string CityId = "";
		public int Value { get { return Hex.Value; } }
		public int Tokens { get { return CalcCityCurrentTokens(); } }
		public int TokenSpots { get { return CalcCityMaxTokens(Hex); } }

		//public List<Side.CompassDirection> HexsidesConnectsTo = new List<Side.CompassDirection>();
		public ArrayList HexsidesConnectsTo = new ArrayList();

		public bool Equals (City testCity)
		{
			return (this == testCity);
		}

		static public City [] GetAllCities (PublicCompany company)
		{
			ArrayList cities = new ArrayList ();
			foreach (GameboardHex hex in company.Game.GameboardHexes)
			{
				if (hex.Cities != null)
					foreach (City city in hex.Cities)
						cities.Add (city);
			}
			City [] ca = new City [cities.Count];
			for (int i=0; i < cities.Count; i++)
				ca[i] = (City) cities[i];
			return (ca);
		}

		static public City [] GetAllTokenedCities (PublicCompany company)
		{
			ArrayList cities = new ArrayList ();
			foreach (GameboardHex hex in company.TokenHexes)
			{
				if (hex.Cities != null)
					// NOT QUITE CORRECT YET
					foreach (City city in hex.Cities)
						cities.Add (city);
			}
			City [] ca = new City [cities.Count];
			for (int i=0; i < cities.Count; i++)
				ca[i] = (City) cities[i];
			return (ca);
		}

		private int CalcCityCurrentTokens()
		{
			// if there's only a single city, it's easy
			if (! Hex.SeperateCities)
				return Hex.Tokens.Count;

			// otherwise we need to check each token to see if it's in this city or the other one
			int count = 0;
			foreach (Token token in Hex.Tokens)
			{
				if (this.HexsidesConnectsTo.Contains(token.LocationInHex.Compass))
					count++;
			}
			return count;
		}

		static public int CalcCityMaxTokens(GameboardHex hex)
		{
			// this is a max max count not a current max count
			int nMaxTokens = hex.MaxTokens;

			if (hex.Tile == null)
				return Math.Min(nMaxTokens, 1);

			// temp hack taken from OperatingRound2.PlaceToken
			if (hex.Tile.TownType == Tile.eTileTownType.City)
			{
				switch (hex.Tile.Color)
				{
					case Tile.eTileColor.Yellow:
						nMaxTokens = 1;
						break;

					case Tile.eTileColor.Green:
						nMaxTokens = 2;

						if ((hex.City == "Toronto") || (hex.City == "New York"))
							nMaxTokens = 1;
						break;

					case Tile.eTileColor.Brown:
						nMaxTokens = 2;

						// NO - for route purposes, Toronto is two 2-spot cities
						//if ((hex.City == "Toronto") || (hex.City == "New York"))
						//	nMaxTokens = 4;
						break;

					case Tile.eTileColor.Gray:
						break;
				}
			}
			return nMaxTokens;
		}
	}
}
